package al206reverseList;

import java.util.List;
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class ReverseList {

/*    public static ListNode reverseList(ListNode head) {
        if (head==null || head.next==null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode after = head.next;

        while (after!=null){
            cur.next = pre;
            pre = cur;
            cur = after;
            after = after.next;
        }
        cur.next=pre;
        pre = cur;
        return pre;
    }*/


    // 递归调用
    public static ListNode reverseList(ListNode head) {
        if (head==null || head.next==null) {
            return head;
        }
        ListNode cur = reverseList(head.next);
        head.next.next=head;
        head.next=null;

        return cur;
    }




    public static void main(String[] args) {
        // 创建一个链表：1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);


        System.out.println("Original List:");
        printList(head);

        // 反转链表
        ListNode reversedHead = ReverseList.reverseList(head);

        System.out.println("Reversed List:");
        printList(reversedHead);
    }

    // 打印链表的辅助方法
    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }

}
